package com.algrithom.stack.monotonousstack;

import java.util.Arrays;
import java.util.Stack;

public class Solution1 {
    
    public static void main(String[] args){
        Solution1 solution1 = new Solution1();
        int[] nums = {2,1,2,4,3};
        System.out.println(Arrays.toString(solution1.nextGreaterElement(nums)));
    }
    
    private int[] nextGreaterElement(int[] nums){
        int len = nums.length;
        int[] result = new int[len];
        Stack<Integer> stack = new Stack<>();
        // 倒着往栈里放
        for (int i = len - 1; i >= 0; i--) {
            // 判定个子高矮
            while (!stack.empty() && stack.peek() <= nums[i]) {
                // 矮个起开，反正也被挡着了。。。
                stack.pop();
            }
            // 这个元素身后的第一个高个
            result[i] = stack.empty() ? -1 : stack.peek();
            // 进队，接受之后的身高判定吧！
            stack.push(nums[i]);
        }
        return result;
    }
}
